The present invention relates to a device for use in an instruction prefetching system of a data processing system in controlling a branch history table arrangement which will presently be described. The device according to this invention can therefore be called a branch history table controlling device.
Various instruction prefetching systems are already known in the art. An example is disclosed in U.S. patent application Ser. No. 286,021 filed Dec. 19, 1988, as a continuation-in-part application by Syuichi Hanatani et al for assignment to the present assignee based on patent applications filed in Japan under Application No. 203,550/1982 and others.
According to the Hanatani et al application, the data processing system includes as usual an instruction address register for memorizing a request address signal representative of an instruction request address. Supplied with the request address signal, an instruction memory produces an instruction signal representative of an instruction from one of its memory addresses that is indicated by the request address signal. The instruction prefetching system is for carrying out instruction prefetch of successively prefetching such instructions along an instruction stream with each instruction prefetched as a current instruction at a time in compliance with the request address signal which is currently memorized in the instruction address register to represent a current request address.
The instruction stream may include a conditional branch instruction which indicates, depending on a condition, one of a branch direction of going to a branch destination or target instruction and a continued direction of not going to the branch destination instruction. The condition is indicated by an outcome obtained after a decoding cycle in which decoding is carried out on the conditional branch instruction prefetched prior to the decoding cycle. Until the decode cycle of the conditional branch instruction, the instruction prefetch proceeds along the branch and the continued directions when prediction is branch successful and branch unsuccessful, respectively.
In order to reduce a loss cycle time which is inevitable when the outcome is found to indicate that the prediction is either incorrect or correct, the instruction prefetching system preferably comprises either a branch history table (BHT) or a decode history table (DHT). The branch history table is revealed in U.S. Pat. No. 3,559,183 issued to Edward H. Sussenguth. The decode history table is revealed in U.S. Pat. No. 4,477,872 issued to Jacques J. Losq et al and is alternatively called a decode-time history table.
The branch history table is for memorizing a plurality of signal pairs. Each signal pair comprises a branch instruction address signal and a branch destination address signal. Previous to prefetch of a conditional branch instruction as a current branch instruction, it is usual that the conditional branch instruction is already prefetched as a previously executed branch instruction and subsequently decoded to produce a historical outcome. Only when the historical outcome indicates that the prediction should have been branch successful, the branch instruction address signal indicates the memory address of the previously executed branch instruction as a previously executed branch instruction address. The branch destination address signal represents a branch destination address which corresponds to the previously executed branch instruction address and is obtained when the previously executed branch instruction was subjected to execution.
In the manner described in the above-cited Hanatani et al application, a retrieving arrangement is connected between the instruction address register and the branch history table for use in retrieving one of the branch instruction address signals of the signal pairs that represents a branch instruction address indicated by the request address signal representative of the current request address. When such a branch instruction address is located, the branch history table produces the branch destination address signal representative of the corresponding branch destination address for use in continuing the instruction prefetch from the branch destination instruction which is represented by an instruction signal produced when the corresponding branch destination address is used in accessing the memory address.
A combination of the branch history table and the retrieving arrangement is herein referred to as the branch history table arrangement. Inasmuch as the signal pairs are memorized only when the historical outcome indicated that the prediction should have been branch successful, the branch history table arrangement is not effective when the prediction should have been branch unsuccessful in connection with a branch instruction which should be prefetched.
The decode history table is for memorizing a plurality of signal pairs like the branch history table. Each signal pair represents a historical branch instruction and a historical outcome which indicates either of branch successful and unsuccessful. The branch destination instruction is therefore fetched after the decode cycle of the conditional branch instruction which is located in the decode history table as one of the previously executed branch instructions represented by the signal pairs. This is undesirable in carrying out the instruction prefetch.